package NowCoder.DataStructrue.Stack;
import java.util.*;

/**
 * HJ43 迷宫问题
 * 中等  通过率：35.12%  时间限制：1秒  空间限制：32M
 * 知识点 查找 dfs 广度优先搜索(BFS)
 * warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
 * 描述
 * 定义一个二维数组 N*M ，如 5 × 5 数组下所示：
 *
 * int maze[5][5] = {
 * 0, 1, 0, 0, 0,
 * 0, 1, 1, 1, 0,
 * 0, 0, 0, 0, 0,
 * 0, 1, 1, 1, 0,
 * 0, 0, 0, 1, 0,
 * };
 *
 * 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。
 * 入口点为[0,0],既第一格是可以走的路。
 *
 * 数据范围： 2≤n,m≤10  ， 输入的内容只包含  0≤val≤1
 *
 * 输入描述：
 * 输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。
 * 数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
 * 输出描述：
 * 左上角到右下角的最短路径，格式如样例所示。
 *
 * 示例1              示例2
 * 输入：             输入：
 * 5 5               5 5
 * 0 1 0 0 0         0 1 0 0 0
 * 0 1 1 1 0         0 1 0 1 0
 * 0 0 0 0 0         0 0 0 0 1
 * 0 1 1 1 0         0 1 1 1 0
 * 0 0 0 1 0         0 0 0 0 0
 * 输出：             输出：
 * (0,0)             (0,0)
 * (1,0)             (1,0)
 * (2,0)             (2,0)
 * (2,1)             (3,0)
 * (2,2)             (4,0)
 * (2,3)             (4,1)
 * (2,4)             (4,2)
 * (3,4)             (4,3)
 * (4,4)             (4,4)
 *
 * 说明：
 * 注意：不能斜着走！！
 * https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&tqId=21266&ru=/exam/oj
 */
public class 迷宫问题_HJ43 {
    //TODO:请重新做这一道题
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] map = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = in.nextInt();
                }
            }

            List<Position> path = new ArrayList<>();
            if(dfs(path, map, 0, 0)) {
                for (Position p : path) {
                    System.out.println("(" + p.x + "," + p.y + ")");
                }
            }
        }
    }

    public static boolean dfs(List<Position> path, int[][] map, int x, int y) {
        int n = map.length;
        int m = map[0].length;
        if (x < 0 || y < 0 || x >= n || y >= m) {
            return false;
        }
        if (map[x][y] == 1) return false;
        if (x == n - 1 && y == m - 1) {
            path.add(new Position(x, y));
            return true;
        }
        path.add(new Position(x, y));
        map[x][y] = 1;
        if (dfs(path, map, x + 1, y)) return true;
        if (dfs(path, map, x, y + 1)) return true;
        if (dfs(path, map, x - 1, y)) return true;
        if (dfs(path, map, x, y - 1)) return true;
        path.remove(path.size() - 1);
        map[x][y] = 0;
        return false;
    }

    public static class Position{
        int x;
        int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
